﻿#region Copyright information
// 
// Copyright © 2005-2013 Yongkee Cho. All rights reserved.
// 
// This code is a part of the Biological Object Library and governed under the terms of the
// GNU Lesser General  Public License (LGPL) version 2.1 which accompanies this distribution.
// For more information on the LGPL, please visit http://bol.codeplex.com/license.
// 
// - Filename: HierarchicalClusterer.cs
// - Author: Yongkee Cho
// - Email: yongkeecho@gmail.com
// - Date Created: 2012-12-08 8:26 AM
// - Last Modified: 2013-01-25 3:59 PM
// 
#endregion
using System;
using System.Collections.Generic;
using System.Linq;

namespace BOL.Algorithms.Clustering
{
    public class HierarchicalClusterer<TPoint> : IConnectivityClusterer<TPoint>
        where TPoint : struct
    {
        #region HierarchicalDirection enum

        public enum HierarchicalDirection
        {
            /// <summary>"bottom up" approach: each observation starts in its own cluster, and pairs of clusters are merged as one moves up the hierarchy.</summary>
            Agglomerative,

            /// <summary>"top down" approach: all observations start in one cluster, and splits are performed recursively as one moves down the hierarchy.</summary>
            Divisive
        }

        #endregion

        #region LinkageCriterion enum

        public enum LinkageCriterion
        {
            /// <summary></summary>
            Single,

            /// <summary></summary>
            Complete,

            /// <summary></summary>
            Average,

            /// <summary></summary>
            Centroid,

            /// <summary></summary>
            Median,

            /// <summary></summary>
            Wald
        }

        #endregion

        #region Public properties

        public Func<IEnumerable<TPoint>, IEnumerable<TPoint>, double> DistanceFunction { get; private set; }
        public LinkageCriterion Criterion { get; private set; }
        public HierarchicalDirection Direction { get; private set; }

        #endregion

        #region Constructor

        public HierarchicalClusterer(Func<IEnumerable<TPoint>, IEnumerable<TPoint>, double> distanceFunction, LinkageCriterion criterion = LinkageCriterion.Centroid, HierarchicalDirection direction = HierarchicalDirection.Agglomerative)
        {
            DistanceFunction = distanceFunction;
            Criterion = criterion;
            Direction = direction;
        }

        #endregion

        #region Private methods

        private void Agglomerate<TSource>(Dictionary<TSource, Dictionary<TSource, double>> distances, ref List<DendrogramNode<TSource>> nodes)
        {
            var count = nodes.Count;

            // for all input nodes, find a node pair with the shortest distance
            var minDistance = double.MaxValue;
            DendrogramNode<TSource> minDistanceNode1 = null;
            DendrogramNode<TSource> minDistanceNode2 = null;

            for (var i = 0; i < count; i++)
                for (var j = i + 1; j < count; j++)
                {
                    var distance = 0.0;
                    var first = nodes[i];
                    var second = nodes[j];
                    var firstSources = first.Elements.ToList();
                    var secondSources = second.Elements.ToList();

                    switch (Criterion)
                    {
                        case LinkageCriterion.Single:
                            distance = firstSources.Min(f => secondSources.Min(s => distances[f][s]));
                            break;
                        case LinkageCriterion.Complete:
                            distance = firstSources.Max(f => secondSources.Max(s => distances[f][s]));
                            break;
                        case LinkageCriterion.Average:
                            distance = firstSources.Sum(f => secondSources.Sum(s => distances[f][s])) / firstSources.Count / secondSources.Count;
                            break;
                        case LinkageCriterion.Centroid:
                            throw new NotImplementedException();
                            //var length = first.First().Length;
                            //var centroid1 = Enumerable.Range(0, length).Select(x => first[x].Average()).ToArray();
                            //var centroid2 = Enumerable.Range(0, length).Select(x => second[x].Average()).ToArray();
                            //distance = DistanceFunction(centroid1, centroid2);
                            //break;
                        case LinkageCriterion.Median:
                            throw new NotImplementedException();
                            //break;
                        case LinkageCriterion.Wald:
                            throw new NotImplementedException();
                            //break;
                    }

                    if (minDistance > distance)
                    {
                        minDistance = distance;
                        minDistanceNode1 = first;
                        minDistanceNode2 = second;
                    }
                }

            // creates node between
            if (minDistanceNode1 != null && minDistanceNode2 != null)
            {
                var maxKey = nodes.Max(x => x.Key);
                var node = new DendrogramNode<TSource>(maxKey + 1, minDistanceNode1.Elements.Concat(minDistanceNode2.Elements));
                node.AddChild(minDistanceNode1);
                node.AddChild(minDistanceNode2);
                nodes.Remove(minDistanceNode1);
                nodes.Remove(minDistanceNode2);
                nodes.Add(node);

                Agglomerate(distances, ref nodes);
            }
        }

        private void Divide<TSource>(Dictionary<TSource, Dictionary<TSource, double>> distances, ref DendrogramNode<TSource> node)
        {
            var elements = node.Elements;
            var count = elements.Count();

            // for all input nodes, find a node pair with the farthest distance
            var maxDistance = double.MinValue;
            IList<TSource> maxDistanceElements1 = null;
            IList<TSource> maxDistanceElements2 = null;
            for (var i = 0; i < count; i++)
            {
                var distance = 0.0;

                // TODO: implement 'list all possible set partitions' problem given partition size.
                // e.g. {1, 2, 3, 4}_2 -> {{1, 2}, {3, 4}}, {{1}, {2, 3, 4}}, {{2}, {1, 3, 4}}, {{3}, {1, 2, 4}}, {{4}, {1, 2, 3}}
                var first = new List<TSource>();
                var second = elements.Except(first).ToList();

                switch (Criterion)
                {
                    case LinkageCriterion.Single:
                        distance = first.Min(f => second.Min(s => distances[f][s]));
                        break;
                    case LinkageCriterion.Complete:
                        distance = first.Max(f => second.Max(s => distances[f][s]));
                        break;
                    case LinkageCriterion.Average:
                        distance = first.Sum(f => second.Sum(s => distances[f][s])) / first.Count / second.Count;
                        break;
                    case LinkageCriterion.Centroid:
                        throw new NotImplementedException();
                        //var length = first.First().Length;
                        //var centroid1 = Enumerable.Range(0, length).Select(x => first[x].Average()).ToArray();
                        //var centroid2 = Enumerable.Range(0, length).Select(x => second[x].Average()).ToArray();
                        //distance = DistanceFunction(centroid1, centroid2);
                        //break;
                    case LinkageCriterion.Median:
                        throw new NotImplementedException();
                    //break;
                    case LinkageCriterion.Wald:
                        throw new NotImplementedException();
                    //break;
                }

                if (maxDistance < distance)
                {
                    maxDistance = distance;
                    maxDistanceElements1 = first;
                    maxDistanceElements2 = second;
                }
            }

            // creates node between
            if (maxDistanceElements1 != null) //&& maxDistanceElements2 != null)
            {
                var key = node.Key;
                var node1 = new DendrogramNode<TSource>(key + 1, maxDistanceElements1);
                var node2 = new DendrogramNode<TSource>(key + 2, maxDistanceElements2);
                node.AddChild(node1);
                node.AddChild(node2);

                if (maxDistanceElements1.Count > 1)
                    Divide(distances, ref node1);
                if (maxDistanceElements2.Count > 1)
                    Divide(distances, ref node2);
            }
        }

        #endregion

        #region Public methods

        public virtual DendrogramNode<TSource> Cluster<TSource>(IEnumerable<TSource> sources, Func<TSource, TPoint[]> pointSelector)
        {
            if (sources == null)
                throw new ArgumentNullException("sources");
            if (pointSelector == null)
                throw new ArgumentNullException("pointSelector");

            var list = sources.ToList();
            var points = list.Select(pointSelector).ToList();
            var numberOfPoints = points.Count;
            if (numberOfPoints == 0)
                throw new ArgumentOutOfRangeException("sources");

            // estimate pairwise distances
            var distances = new Dictionary<TSource, Dictionary<TSource, double>>();
            for (var i = 0; i < numberOfPoints; i++)
                distances.Add(list[i], new Dictionary<TSource, double>());

            for (var i = 0; i < numberOfPoints; i++)
            {
                var firstPoint = points[i];
                for (var j = i + 1; j < numberOfPoints; j++)
                {
                    var secondPoint = points[j];
                    var distance = DistanceFunction(firstPoint, secondPoint);

                    distances[list[i]].Add(list[j], distance);
                    distances[list[j]].Add(list[i], distance);
                }
            }

            if (Direction == HierarchicalDirection.Divisive)
            {
                var rootNode = new DendrogramNode<TSource>(0, list);
                Divide(distances, ref rootNode);

                return rootNode;
            }

            var k = 0;
            var leafNodes = list.Select(x => new DendrogramNode<TSource>(k++, new[] {x})).ToList();
            Agglomerate(distances, ref leafNodes);

            return leafNodes.First();
        }

        IEnumerable<IGrouping<int, TSource>> IClusterer<TPoint>.Cluster<TSource>(IEnumerable<TSource> sources, Func<TSource, TPoint[]> pointSelector)
        {
            return Cluster(sources, pointSelector).Children;
        }

        #endregion

        #region Object overriden

        public string ToString<TSource>(DendrogramNode<TSource> rootNode)
        {
            var prefix = String.Empty;
            rootNode.ToString(ref prefix, 0);
            return prefix;
        }

        #endregion
    }
}